package 力扣._00周赛._146双周赛.问题2;

class Solution {
    public int countPathsWithXorValue(int[][] grid, int k) {
        int mod = 1000000007;
        int m = grid.length, n = grid[0].length;
        // grid[i][j] : 0~16 , 异或值最大为15

        // dp[i][j][l]: 到达(i, j)位置时，异或值为l的路径数
        int[][][] dp = new int[m][n][16];

        // 初始化
        dp[0][0][grid[0][0]] = 1;
        // 最左边一列
        int t = 0;
        for (int i = 0; i < m; i++) {
            t ^= grid[i][0];
            dp[i][0][t] = 1;
        }
        // 最上边一行
        t = 0;
        for (int i = 0; i < n; i++) {
            t ^= grid[0][i];
            dp[0][i][t] = 1;
        }


        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                // 从左边过来
                for(int l = 0;l<16;l++){
                    int l_n = dp[i-1][j][l];
                    if(l_n != 0){
                        dp[i][j][l^grid[i][j]] = (dp[i][j][l^grid[i][j]] + l_n) % mod;
                    }
                }
                // 从上边过来
                for(int l = 0;l<16;l++){
                    int l_n = dp[i][j-1][l];
                    if(l_n != 0){
                        dp[i][j][l^grid[i][j]] = (dp[i][j][l^grid[i][j]] + l_n) % mod;
                    }
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for(int l = 0;l<16;l++){
                    System.out.print(dp[i][j][l] + " ");
                }
                System.out.print(",");

            }
            System.out.println();
        }
        return dp[m-1][n-1][k];

    }

    public static void main(String[] args) {
        // [[2,1,5],[7,10,0],[12,6,4]]
        //11©leetcode

        int[][] grid = new int[][]{{2,1,5},{7,10,0},{12,6,4}};
        int k = 11;
        Solution solution = new Solution();
        System.out.println(solution.countPathsWithXorValue(grid, k));
    }
}